#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"

void HeapInit(Heap* pp)
{
	assert(pp);
	pp->arr = NULL;
	pp->size = pp->capacity = 0;
}

void HeapDestory(Heap* pp)
{
	assert(pp);
	free(pp->arr);
	pp->arr = NULL;
	pp->size = pp->capacity = 0;
}

void HeapPrint(Heap* pp)
{
	assert(pp);
	int i = 0;
	for (i = 0; i < pp->size; i++)
	{
		printf("%d->", pp->arr[i]);
	}
	printf("\n");
}

void HeapCheckCapacity(Heap* pp)
{
	assert(pp);
	if (pp->size == pp->capacity)
	{
		int newcapacity = pp->size == 0 ? 4 : 2 * pp->capacity;
		HeapDataType* tmp = (HeapDataType*)realloc(pp->arr, sizeof(Heap) * newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail!\n");
			exit(-1);
		}
		else
		{
			pp->arr = tmp;
			pp->capacity = newcapacity;
		}
	}
}

void AdjustUp(HeapDataType* pp, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (pp[child] > pp[parent])
		{
			HeapSwap(&pp[child], &pp[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HeapSwap(HeapDataType* p1, HeapDataType* p2)
{
	HeapDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void HeapPush(Heap* pp, HeapDataType val)
{
	assert(pp);
	HeapCheckCapacity(pp);
	pp->arr[pp->size] = val;
	pp->size++;

	AdjustUp(pp->arr, pp->size - 1);
}

void AdjustDown(HeapDataType* pp, int n, int parent)
{
	int minChild = 2 * parent + 1;
	while (minChild < n)
	{
		if (pp[minChild] > pp[minChild + 1] && minChild + 1 < n)
		{
			minChild++; 
		}

		if (pp[minChild] < pp[parent])
		{
			HeapSwap(&pp[minChild], &pp[parent]);
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapCreate(Heap* pp, HeapDataType* arr, int n)
{
	assert(pp);
	pp->arr = (HeapDataType*)malloc(sizeof(HeapDataType) * n);
	if (pp->arr == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	memcpy(pp->arr, arr, sizeof(HeapDataType) * n);
	pp->size = pp->capacity = n;
	int parentNode = (n - 1 - 1) / 2;

	for (int i = parentNode; i >= 0; i--)
	{
		AdjustDown(pp->arr, n, i);
	}
}

void HeapPop(Heap* pp)
{
	assert(pp);
	assert(pp->size);
	HeapSwap(&pp->arr[0], &pp->arr[pp->size - 1]);
	pp->size--;

	AdjustDown(pp->arr, pp->size, 0);
}

HeapDataType HeapTop(Heap* pp)
{
	assert(pp);
	assert(pp->size);

	return pp->arr[0];
}

bool HeapEmpty(Heap* pp)
{
	assert(pp);
	return pp->size == 0;
}

int HeapSize(Heap* pp)
{
	assert(pp);
	return pp->size;
}